二叉树——用递归或循环的方式实现二叉树遍历

Posted on | In ,

递归即使利用函数栈来保存信息。
非递归：利用自己申请的数据结构来代替函数栈.

实现：

  1. 申请一个新栈stack，将头节点head压入stack.。
  2. 从stack中弹出栈顶节点，记为cur，然后打印cur的值。将cur右孩子（不为空的话）压入stack中，再将cur的左孩子（不为空的话）压入stack。

重复步骤2（压入一次右孩子、左孩子，就弹出栈顶元素），直到stack为空，结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class TreeNode{
	public int data;
	public TreeNodeleft;
	public TreeNoderight;
	public TreeNode(int data){
		this.data = data;
	}
}
//利用递归进行先序遍历：根、左、右
public void preOrderRecur(TreeNodehead){
	if (head == null){
		return;
	}
	System.out.print(head.data + " " );
	preOrderRcur(head.left);
	prOrderRecur(head.right);
}
//利用递归进行中序遍历：左、根、右
public void preOrderRecur(TreeNodehead){
	if (head == null){
		return;
	}
	preOrderRcur(head.left);
	System.out.print(head.data + " " );
	prOrderRecur(head.right);
}
//利用递归进行后序遍历：左、右、根
public void preOrderRecur(TreeNodehead){
	if (head == null){
		return;
	}
	preOrderRcur(head.left);
	prOrderRecur(head.right);
	System.out.print(head.data + " " );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//利用循环实现二叉树遍历
public void preOrderUnrecur(TreeNodehead){
	if (head == null){
		return;
	}
	Stack<TreeNode> stack = new Stack<>();
	stack.putsh(head);
	while(!stack.isEmpty()){
		cur = stack.pop();
		System.out.print(head.data +" ");
		if (cur.right != null){
			stack.push(cur.right);
		}
		if (cur.left != null) {
			stack.push(cur.left);
		}
	}
}